def bellman_ford(s):
    d[s] = 0
    for i in xrange(len(V) - 1): 
        for e in xrange(m):
            u = x[e]
            v = y[e]
            if d[v] > d[u] + w[e]:
                d[v] = d[u] + w[e]
    z = None # a node in neg cycle
    for e in xrange(m):
        u = x[e]
        v = y[e]
        if d[v] > d[u] + w[e]:
            z = v
            break
    if z is not None:
        dfs(z)

vis = set()
def dfs(v):
    d[v] = '-inf'
    vis.add(v)
    for u, _ in Adj[v]:
        if u not in vis:
            dfs(u)

if __name__=='__main__':
    from sys import maxint
    from pprint import pprint
    Adj = [[(1,10)],[(2,1)],[(1,-2),(3,6)],[(4,3)],[(5,7)],[]]
    print 'Adj: Adj[u] stores (v,w[u,v])'
    pprint(Adj)
    
    V = xrange(len(Adj))
    m = 0 # # of edges
    x = {}
    y = {}
    w = {}
    for u in V:
        for v, ww in Adj[u]:
            x[m] = u
            y[m] = v
            w[m] = ww
            m += 1
    
    d = [maxint] * len(V)
    bellman_ford(0)
    print 'd :', d